Evolvable Hardware or EHW is reconfigurable hardware that self-configures under the control of an evolutionary algorithm. In evolutionary electronics, the search for an electronic circuit reconfiguration can be made in software and the final solution downloaded or become a blueprint for hardware, which is referred to as extrinsic evolution. Alternatively, evolution can be performed directly in hardware, referred to as intrinsic evolution. With intrinsic evolution, solutions may be evolved directly on a chip.
The main steps of evolutionary synthesis are illustrated in FIG. 1. First, a population of chromosomes is randomly generated. The chromosomes are converted into circuit models for extrinsic EHW, or control bit strings downloaded to programmable hardware intrinsic EHW. Circuit responses are compared against specifications of a target response, and individuals are ranked based on how close they come to satisfying it. In preparation for a new iteration loop, a new population of individuals is generated from the pool of best individuals in the previous generation, some of these individuals are taken as they were and some are modified by genetic operators such as chromosome crossover and mutation. This process is repeated for many generations, and results in increasingly better individuals. Such a process is usually stopped after a number of generations, or when the closeness to the target response has reached a sufficient degree. One of several solutions may be found among the individuals of the last generation.
A variety of circuits have been synthesized through extrinsic evolutionary means. For example, Koza et al., in U.S. Pat. No. 5,867,397, issued on Feb. 2, 1999, entitled METHOD AND APPARATUS FOR AUTOMATED DESIGN OF COMPLEX STRUCTURES USING GENETIC PROGRAMMING, herein incorporated by reference in its entirety, used Genetic Programming (GP) to grow an “embryonic” circuit to a circuit that satisfies desired requirements. This approach was used for evolving a variety of circuits, including filters and computational circuits. An alternative encoding technique using a linear representation, which has the advantage of reduced computational load, has been used in for automated filter design.
With these extrinsic approaches, though, evolutions of analog circuits were performed in simulations, without concern of a physical implementation, but rather, as a proof-of-concept that evolution can lead to designs that compete or even exceed the performance of human designs. Although in principle, one can test their validity in circuits built from discrete components, or in an ASIC, no analog programmable devices exist that would support the implementation of the resulting design. Thus, these approaches do not provide a practical solution to intrinsic evolution.
Intrinsic evolution can speed-up the search for a solution circuit by a few orders of magnitude compared to evolution in software simulations, specifically if one simulates large, complex analog circuits, and if the circuit response is rapid. Moreover, since the software simulation relies on models of physical hardware with limited accuracy, a solution evolved in software may behave differently when downloaded in programmable hardware; such mismatches are avoided when evolution takes place directly in hardware. Further, unlike software evaluation where more complex circuitry and more accurate modeling takes longer to evaluate, hardware evolution scales well with both size of the circuits and model accuracy, thus providing less significant increases in evaluation time.
Although reconfigurable devices exist, they have a limited range of possible applications. On-chip evolution was demonstrated by A. Thompson, in Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), MIT Press, herein incorporated by reference in its entirety, using a Field Programmable Gate Array or FPGA as a programmable digital device, and a Genetic Algorithm or GA as the evolutionary mechanism.
Such a technique using gate arrays, however, is not practical for analog circuit evolution. Logical gates are not good elementary building blocks for analog circuits as they are designed optimized for logical/binary behaviors. For example, transistor interconnections that are designed to facilitate digital logic signals and flows do not necessarily provide good analog response and signal flow. The usage of the gate array for evolution can result in exploitation by evolution, of parasitic and unintended signal paths and functioning modes for the components. As a result, circuits may evolve in one region of a chip that can not be replicated in other parts, or on other chips, although the same genetic code is used.
Moreover, conventional on chip evolution has not provided sufficient granularity for practical applications. While several levels of granularity are in use, the most common digital devices are configurable at the gate-level. In the analog programmable devices, such as in Field Programmable Analog Arrays or FPAAs, the reconfigurable active elements are Operational Amplifiers, which have only very coarse granularity and little functionality with good precision, thus having only a limited range of possible applications.
Analog circuit design has been lost as a technique for computing because analog circuits were not easily programmable, and required precise components with no drifts. If the evolutionary mechanism and process proves sufficiently powerful for evolving complex analog circuits, then its combination with reconfigurable analog devices potentially will be able to capture the benefits of analog in new applications. As such, the potential of analog processing is much greater than what is able to be exploited today.
Analog circuitry has advantages in cost, size and power consumption (as compared to digital circuitry) and can directly process signals that are continual in time and amplitude. Even a single transistor has many functions such as generation of square, square-root, exponential and logarithmic functions, voltage-controlled current sources; analog multiplication of voltages, and short term and long term analog storage. As such, the basic combinations of transistors offer a rich repertoire of linear and nonlinear operators available for local and collective analog processing. Using evolution, the benefits of analog processing can be exploited, while its disadvantages reduced or even eliminated.
Also, it has been recognized by the inventors herein that evolutionary searches may perform significantly better with analog than with digital circuitry. A possible explanation lies in the fact that analog behaviors have relatively smoother spaces, which is better for the evolutionary search. Thus, new perspectives are possible: evolutionary searches offering automatic programming; sufficiently precise equivalent components could be obtained if the programmable analog components offer controllably of their operating points; and drifts that can be compensated for by adjusting operating points or, if the drifts are too strong, by a new search for a different optimal circuit configuration and operating point. Moreover, analog computation on simple low-power circuits can boost emerging applications areas of “smart matter” and distributed high bandwidth adaptive sensing.
Furthermore, a hardware implementation also offers a big advantage in evaluation time for a circuit; the time for evaluation is determined by the goal function. For example, considering an A/D converter operating at a 100 kHz sampling rate the electronic response of the A/D converter is available within 10 microseconds, compared to (an over-optimistic) 1 second on a fast computer running SPICE; this advantage increases with the complexity of the circuits. In this case, the 105 speedup would allow evaluations of populations of millions of individuals in seconds instead of days. Moreover, the higher the frequency at which a circuit needs to function, the shorter is its evaluation time, making the design of very high frequency circuits an excellent candidate for intrinsic evolutionary design.
In the above-described software modeling approaches, a particular type of model is selected to perform an evolutionary search of a population of circuits meeting predefined behavioral requirements. In an extrinsic simulation, software models simulate dynamic behavior of candidate circuits. The response of each candidate circuit to a predetermined stimulus is compared against a desired response, and the difference is quantified as the fitness function. As a simple example, an analog circuit may be required that produces a gaussian-shaped output voltage in response to a ramped input voltage. A summation over time of the differences between the desired output voltage and the actual output voltage of a candidate circuit may be used as the fitness function (or “score”) of the candidate circuit. The evolutionary process includes testing the response of each candidate circuit and ranking them by the resulting scores. The candidates having the best fitness functions or scores are retained for the next iteration while those with the worst scores are eliminated from subsequent iterations of the evolutionary process.
In extrinsic or software modeling, the choice of software model determines the reproducability of the model in hardware. In either type of modeling, the choice is typically between a more robust model and a less robust model. In extrinsic modeling, the more robust software models are more complex but exhibit more realistic behavior that better follows real hardware behavior. In intrinsic modeling, the more robust models have more hardware switches (for example) so that more choices of circuit configurations are available. In either case, the choice of model determines the speed with which the simulation and search can occur and whether the simulation can converge to a solution within a practical time frame. In fact, there is a tradeoff between speed of convergence and hardware reproducability. For example, in software modeling, the more robust models are more faithful to real hardware behavior but require solution of a larger number of equations, which lengthens the time required for convergence and may prevent convergence. In hardware modeling, the more robust models correspond to a larger search space, which typically lengthens the time of the search or convergence, and may prevent convergence within a practical time.
One way around this problem is to use simpler models whose convergence is sure and rapid. For example, in software modeling, one could use a very simple software model of each circuit. There are many levels of SPICE models from which one may choose to perform a simulation and search, and a simpler or lower resolution model would correspond to a lower level of SPICE modeling (e.g., SPICE level 5 instead of level 7). This solution may better promote convergence when modeling a very complex system, such as an analog-to-digital converter, but the lower resolution models typically cannot be relied upon to provide solutions or circuits that, when reproduced in hardware, exhibit the simulated behavior. A similar dilemma is present in hardware modeling. For example, one could employ reconfigurable hardware in intrinsic modeling in which the number of switches is reduced (i.e., some switches are frozen in pre-defined states) to limit the number of choices or reduce the search space. However, such a limitation may exclude the candidate circuits that represent the only solutions to a particular search problem, or at least the best solutions.